{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #所有可能的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: allPathsSourceTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有可能的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个有&nbsp;<code>n</code>&nbsp;个节点的有向无环图，用二维数组&nbsp;<code>graph</code>&nbsp;表示，请找到所有从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n-1</code>&nbsp;的路径并输出（不要求按顺序）。</p>\n",
    "\n",
    "<p><code>graph</code>&nbsp;的第 <code>i</code> 个数组中的单元都表示有向图中 <code>i</code>&nbsp;号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a&rarr;b 你就不能从 b&rarr;a ），若为空，就是没有下一个节点了。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/28/all_1.jpg\" style=\"height: 242px; width: 242px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2],[3],[3],[]]\n",
    "<strong>输出：</strong>[[0,1,3],[0,2,3]]\n",
    "<strong>解释：</strong>有两条路径 0 -&gt; 1 -&gt; 3 和 0 -&gt; 2 -&gt; 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/28/all_2.jpg\" style=\"height: 301px; width: 423px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[4,3,1],[3,2,4],[3],[4],[]]\n",
    "<strong>输出：</strong>[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1],[]]\n",
    "<strong>输出：</strong>[[0,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2,3],[2],[3],[]]\n",
    "<strong>输出：</strong>[[0,1,2,3],[0,2,3],[0,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,3],[2],[3],[]]\n",
    "<strong>输出：</strong>[[0,1,2,3],[0,3]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == graph.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>0 &lt;= graph[i][j] &lt; n</code></li>\n",
    "\t<li><code>graph[i][j] != i</code>&nbsp;</li>\n",
    "\t<li>保证输入为有向无环图 <code>(GAD)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 797&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/all-paths-from-source-to-target/\">https://leetcode-cn.com/problems/all-paths-from-source-to-target/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bP4bmD](https://leetcode.cn/problems/bP4bmD/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bP4bmD](https://leetcode.cn/problems/bP4bmD/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3],[3],[]]', '[[4,3,1],[3,2,4],[3],[4],[]]', '[[1],[]]', '[[1,2,3],[2],[3],[]]', '[[1,3],[2],[3],[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def dfs(source, graph, path, ans):\n",
    "            path.append(source)\n",
    "            ### source 为当前访问的节点\n",
    "            if source == len(graph) -1:\n",
    "                # 如果当前节点为 n-1 把path加入ans\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            else:\n",
    "                for nex in graph[source]:\n",
    "                    dfs(nex, graph, path, ans)\n",
    "                    path.pop()      \n",
    "\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "        dfs(0, graph, path, ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        reverse_graph=[[]for _ in range(len(graph))]\n",
    "        for i in range(len(graph)):\n",
    "            for pos in graph[i]:\n",
    "                reverse_graph[pos].append(i)\n",
    "        paths=[]\n",
    "        def add_ans(path,pos):\n",
    "            if pos==0:\n",
    "                paths.append(path)\n",
    "                return \n",
    "            for x in reverse_graph[pos]:\n",
    "                add_ans(path+[x],x)\n",
    "\n",
    "        add_ans([],len(graph)-1)\n",
    "        return [x[::-1]+[len(graph)-1] for x in paths]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def back_track(self,graph,node_ind):\n",
    "        if node_ind == len(graph) - 1:\n",
    "            self.ans.append(self.path[:])\n",
    "            return\n",
    "        for i in range(0,len(graph[node_ind])):\n",
    "            self.path.append(graph[node_ind][i])\n",
    "            next_ind = graph[node_ind][i]\n",
    "            self.back_track(graph, next_ind)\n",
    "            self.path.pop()\n",
    "        return\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        self.path = [0]\n",
    "        self.back_track(graph, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    \n",
    "    def dfs(self, graph, i, tmp):\n",
    "        if i==len(graph)-1:\n",
    "            self.res.append(tmp)\n",
    "            return\n",
    "        if len(graph[i])==0:\n",
    "            return\n",
    "        for j in graph[i]:\n",
    "            self.dfs(graph, j, tmp+[j]) \n",
    "\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.dfs(graph,0,[0])\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        self.res = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, graph: List[List[int]], s, path: List[int]):\n",
    "        path.append(s)\n",
    "        if s == len(graph) - 1:\n",
    "            self.res.append(path[:])\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 深度遍历邻接矩阵\n",
    "        def dfs(start, graph,path,res):\n",
    "            if start == len(graph)-1:\n",
    "                res.append(path[:]) # append的是[:],即克隆\n",
    "                return\n",
    "            for i in graph[start]:\n",
    "                # 把当前节点加入路径中\n",
    "                path.append(i)\n",
    "                dfs(i, graph,path,res)\n",
    "                path.pop() # 回溯\n",
    "        res = []\n",
    "        path = [0]\n",
    "        dfs(0,graph,path,res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res, n = [[0]],len(graph)\n",
    "        stack,ans = [0], []\n",
    "        while stack:\n",
    "            m = len(stack)\n",
    "            tmp = []\n",
    "            for i in range(m):\n",
    "                t = stack.pop(0)\n",
    "                for num in graph[t]:\n",
    "                    if num == n-1:\n",
    "                        ans.append(res[i]+[num])\n",
    "                    tmp.append(res[i]+[num])\n",
    "                    stack.append(num)\n",
    "            res = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def haha(self,graph,i,lujing):\n",
    "        for j in graph[i]:\n",
    "            if(j == len(graph)-1):\n",
    "                self.ans.append(lujing+[j])\n",
    "            if(j not in lujing):\n",
    "                self.haha(graph,j,lujing+[j])\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        self.haha(graph,0,[0])\n",
    "        return(self.ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        path = [0]\n",
    "        self.traverse(0, graph, path)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, p, graph, path):\n",
    "        if p==len(graph)-1:\n",
    "            self.res.append(path[:])\n",
    "            return\n",
    "        for v in graph[p]:\n",
    "            path.append(v)\n",
    "            self.traverse(v, graph, path)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录所有路径\n",
    "        self.res = []\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 维护递归过程中经过的路径\n",
    "        path = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    # 图的遍历框架\n",
    "    def traverse(self, graph: List[List[int]], s: int, path: List[int]):\n",
    "        # 添加节点 s 到路径\n",
    "        path.append(s)\n",
    "\n",
    "        n = len(graph)\n",
    "        if s == n - 1:\n",
    "            # 到达终点\n",
    "            self.res.append(path.copy())\n",
    "            # 可以在这直接 return，但要 removeLast 正确维护 path\n",
    "            # path.pop()\n",
    "            # return\n",
    "            # 不 return 也可以，因为图中不包含环，不会出现无限递归\n",
    "\n",
    "        # 递归每个相邻节点\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        \n",
    "        # 从路径移出节点 s\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, graph, i):\n",
    "        self.onpath.append(i)\n",
    "        if i==self.number - 1:\n",
    "            self.res.append(self.onpath[:])\n",
    "        for node in graph[i]:\n",
    "            self.dfs(graph, node)\n",
    "        self.onpath.pop(-1)\n",
    "\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        self.number = len(graph)\n",
    "        self.res = []\n",
    "        self.onpath = []\n",
    "        self.visited = [False]*self.number\n",
    "        self.dfs(graph, 0)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        if not graph:\n",
    "            return []\n",
    "        return self.dfs(graph,0,[0],[])\n",
    "    def dfs(self,graph,x,path,res):\n",
    "        if x==len(graph)-1:\n",
    "            res.append(path[:])\n",
    "            return  \n",
    "        for node in graph[x]:\n",
    "            path.append(node)\n",
    "            self.dfs(graph,node,path,res)\n",
    "            path.pop()\n",
    "        return res \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, graph, s, path):\n",
    "        path.append(s)\n",
    "        n = len(graph)\n",
    "        if s == n-1:\n",
    "            self.res.append(path[:])\n",
    "            path.pop()\n",
    "            return\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        q = deque()\n",
    "        q.append([0])\n",
    "        ans = []\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            for i in graph[node[-1]]:\n",
    "                if i == len(graph) - 1:\n",
    "                    ans.append(node + [i])\n",
    "                else:\n",
    "                    q.append(node + [i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        pathes = []\n",
    "        n = len(graph)\n",
    "        st_node = 0\n",
    "        ed_node = n - 1\n",
    "        queue = []\n",
    "\n",
    "        queue.append([st_node])\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            cur_path = queue.pop(0)\n",
    "            cur_node = cur_path[-1]\n",
    "\n",
    "            if cur_node == ed_node:\n",
    "                pathes.append(cur_path)\n",
    "\n",
    "            for i in graph[cur_node]:\n",
    "                if  i not in cur_path:\n",
    "                    queue.append(cur_path + [i]) \n",
    "        \n",
    "        return pathes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        path = []\n",
    "        dfs(0, graph, path, ret)\n",
    "        return ret\n",
    "\n",
    "def dfs(source, graph, path, ret):\n",
    "    path.append(source)\n",
    "    if source == len(graph) - 1:\n",
    "        ret.append(path[:])\n",
    "    for n in graph[source]:\n",
    "        dfs(n, graph, path, ret)\n",
    "    path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录所有路径\n",
    "        self.res = []\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 维护递归过程中经过的路径\n",
    "        path = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    # 图的遍历框架\n",
    "    def traverse(self, graph: List[List[int]], s: int, path: List[int]):\n",
    "        # 添加节点 s 到路径\n",
    "        path.append(s)\n",
    "\n",
    "        n = len(graph)\n",
    "        if s == n - 1:\n",
    "            # 到达终点\n",
    "            self.res.append(path.copy())\n",
    "            # 可以在这直接 return，但要 removeLast 正确维护 path\n",
    "            # path.pop()\n",
    "            # return\n",
    "            # 不 return 也可以，因为图中不包含环，不会出现无限递归\n",
    "\n",
    "        # 递归每个相邻节点\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        \n",
    "        # 从路径移出节点 s\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph) :\n",
    "        res=[]\n",
    "        now=[0]\n",
    "        self.findall(graph,res,now,0)\n",
    "        return res\n",
    "\n",
    "    def findall(self,graph,res,now,i):\n",
    "        if i==len(graph)-1:\n",
    "            res.append(now[:])\n",
    "            return 0\n",
    "        for j in graph[i]:\n",
    "            now.append(j)\n",
    "            self.findall(graph,res,now,j)\n",
    "            now.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        # Solution: Depth-first Search\n",
    "        n = len(graph)\n",
    "\n",
    "        stack = [[0]]\n",
    "\n",
    "        while stack:\n",
    "            \n",
    "            cur = stack.pop()\n",
    "            last_node = cur[-1]\n",
    "\n",
    "            for node in graph[last_node]:\n",
    "                \n",
    "                if node == n - 1:\n",
    "                    res.append(cur + [node])\n",
    "                elif node in cur:\n",
    "                    continue\n",
    "                else:\n",
    "                    stack.append(cur + [node])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res, path = [], []\n",
    "        n = len(graph)\n",
    "        for i in graph[0]:\n",
    "            if i == n-1:\n",
    "                res.append([0, i])\n",
    "            else:\n",
    "                path.append([0, i])\n",
    "        queue = collections.deque(path)\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                ppath = queue.popleft()\n",
    "                for node in graph[ppath[-1]]:\n",
    "                    if node == n - 1:\n",
    "                        res.append(ppath + [node])\n",
    "                    else:\n",
    "                        queue.append(ppath + [node])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        q = deque([(0, [0])])\n",
    "        while q:\n",
    "            x, p = q.popleft()\n",
    "            if x == len(graph) - 1:\n",
    "                ans.append(p)\n",
    "            for y in graph[x]:\n",
    "                q.append((y, p+[y]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录所有路径\n",
    "        self.res = []\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 维护递归过程中经过的路径\n",
    "        path = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    # 图的遍历框架\n",
    "    def traverse(self, graph: List[List[int]], s: int, path: List[int]):\n",
    "        # 添加节点 s 到路径\n",
    "        path.append(s)\n",
    "\n",
    "        n = len(graph)\n",
    "        if s == n - 1:\n",
    "            # 到达终点\n",
    "            self.res.append(path.copy())\n",
    "            # 可以在这直接 return，但要 removeLast 正确维护 path\n",
    "            # path.pop()\n",
    "            # return\n",
    "            # 不 return 也可以，因为图中不包含环，不会出现无限递归\n",
    "\n",
    "        # 递归每个相邻节点\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        \n",
    "        # 从路径移出节点 s\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        ans=list() #the answer list, all possible path\n",
    "        stack=list()\n",
    "        tmp=list()\n",
    "        def dfs(x):\n",
    "            if x==len(graph)-1:\n",
    "                ans.append(stack[:]) #stack[:]和stack区别?\n",
    "                return \n",
    "\n",
    "            for y in graph[x]: #[1,2]\n",
    "                stack.append(y) #[0,1] 前进\n",
    "                dfs(y) #for 1, run dfs, expand the solution tree for y\n",
    "                stack.pop() #after dfs pop it.  回溯\n",
    "        \n",
    "        stack.append(0)\n",
    "        dfs(0) #start from root\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        target = len(graph)-1\n",
    "        # seen = collections.defaultdict(list)\n",
    "        q = deque([(\"\", 0)])\n",
    "        while q:\n",
    "            road, step = q.popleft()\n",
    "            if step == target:\n",
    "                res.append(list(map(int, road[1:].split(',')))+[target])\n",
    "            for i in graph[step]:\n",
    "                # if i not in seen:\n",
    "                q.append((road+','+str(step), i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        stk = list()\n",
    "\n",
    "        def dfs(x:int):\n",
    "            if x==len(graph)-1:\n",
    "                ans.append(stk[:])\n",
    "                return\n",
    "\n",
    "            for  y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.path = [0]\n",
    "\n",
    "    def dfs(self, graph, root):\n",
    "        if root == len(graph)-1:\n",
    "            self.res.append(self.path[:])\n",
    "            return \n",
    "        \n",
    "        for node in graph[root]:\n",
    "            self.path.append(node)\n",
    "            self.dfs(graph, node)\n",
    "            self.path.pop()\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        if not graph:\n",
    "            return []\n",
    "        self.dfs(graph, 0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        result=[]\n",
    "        n=len(graph)\n",
    "\n",
    "        def traverse(path,node):\n",
    "            path.append(node)\n",
    "\n",
    "            if node==n-1:\n",
    "                result.append(path[:])\n",
    "                path.pop()\n",
    "                return\n",
    "\n",
    "            for cur_node in graph[node]:\n",
    "                traverse(path,cur_node)\n",
    "            \n",
    "            path.pop()\n",
    "        \n",
    "        traverse([],0)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        stk = [0]\n",
    "        res = []\n",
    "\n",
    "        def dfs(graph, stk, res, x):\n",
    "            if stk[-1] == len(graph) - 1:\n",
    "                res.append(stk)\n",
    "            \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(graph, stk.copy(), res, y)\n",
    "                stk.pop()\n",
    "\n",
    "        dfs(graph, stk, res, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        res = []\n",
    "        result = []\n",
    "        def dfs(i:int):\n",
    "            if i == n-1:\n",
    "                result.append(res[:])\n",
    "                return\n",
    "            else:\n",
    "                for x in graph[i]:\n",
    "                    res.append(x)\n",
    "                    dfs(x)\n",
    "                    res.pop()\n",
    "    \n",
    "        res.append(0)\n",
    "        dfs(0)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        stk=[]\n",
    "        def dfs(x):\n",
    "            if x==len(graph)-1:\n",
    "                ans.append(stk[:])\n",
    "                return \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        q = collections.deque()\n",
    "        q.append([0,[0]])\n",
    "        while q:\n",
    "            cur, path = q.popleft()\n",
    "            if cur == len(graph) - 1:\n",
    "                ans.append(path)\n",
    "            for i in graph[cur]:\n",
    "                nextPath = path + [i]\n",
    "                q.append([i, nextPath])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def backtrace(x: int) -> None:\n",
    "            nonlocal res\n",
    "            nonlocal path\n",
    "            if x == n - 1:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            for y in graph[x]:\n",
    "                path.append(y)\n",
    "                backtrace(y)\n",
    "                path.pop()\n",
    "            \n",
    "        n = len(graph)\n",
    "        res = []\n",
    "        path = [0]\n",
    "        backtrace(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        stack = list()\n",
    "        \n",
    "        def dfs(n):\n",
    "            if n == len(graph) - 1:\n",
    "                ans.append(stack[:])\n",
    "                return\n",
    "            for pth in graph[n]:\n",
    "                stack.append(pth)\n",
    "                dfs(pth)\n",
    "                stack.pop()\n",
    "        stack.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        def DFS(cur_path):\n",
    "            if cur_path[-1] == n - 1:\n",
    "                ans.append(cur_path[:])\n",
    "            else:\n",
    "                cur_node = cur_path[-1]\n",
    "                for child in graph[cur_node]:\n",
    "                    if not visited[child]:\n",
    "                        visited[child] = True\n",
    "                        DFS(cur_path + [child])\n",
    "                        visited[child] = False\n",
    "\n",
    "        n, ans = len(graph), []\n",
    "        visited = [False] * n\n",
    "        DFS([0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(graph)\n",
    "        def dfs(x: int, path: list[int]) -> None:\n",
    "            if x == n - 1:\n",
    "                ans.append(path)\n",
    "            for v in graph[x]:\n",
    "                dfs(v, path + [v])\n",
    "        dfs(0, [0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录所有路径\n",
    "        self.res = []\n",
    "\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # 维护递归过程中经过的路径\n",
    "        path = []\n",
    "        self.traverse(graph, 0, path)\n",
    "        return self.res\n",
    "\n",
    "    # 图的遍历框架\n",
    "    def traverse(self, graph: List[List[int]], s: int, path: List[int]):\n",
    "        # 添加节点 s 到路径\n",
    "        path.append(s)\n",
    "\n",
    "        n = len(graph)\n",
    "        if s == n - 1:\n",
    "            # 到达终点\n",
    "            self.res.append(path.copy())\n",
    "            # 可以在这直接 return，但要 removeLast 正确维护 path\n",
    "            # path.pop()\n",
    "            # return\n",
    "            # 不 return 也可以，因为图中不包含环，不会出现无限递归\n",
    "\n",
    "        # 递归每个相邻节点\n",
    "        for v in graph[s]:\n",
    "            self.traverse(graph, v, path)\n",
    "        \n",
    "        # 从路径移出节点 s\n",
    "        path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        def dfs(v, path):\n",
    "            if v == n - 1:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for w in graph[v]:\n",
    "                path.append(w)\n",
    "                dfs(w, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, [0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        road = [0]\n",
    "\n",
    "        def dfs(x):\n",
    "            if x==len(graph)-1:\n",
    "                res.append(road[:])\n",
    "            \n",
    "            for i in graph[x]:\n",
    "                road.append(i)\n",
    "                dfs(i)\n",
    "                road.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        stk = list()\n",
    "\n",
    "        def dfs(x: int):\n",
    "            if x == len(graph) - 1:\n",
    "                ans.append(stk[:])\n",
    "                return\n",
    "            \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        \n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        def dfs(tmp, arr, target):\n",
    "            for a in arr:\n",
    "                if a == target:\n",
    "                    ret.append(tmp+[a])\n",
    "                dfs(tmp+[a], graph[a], target)\n",
    "        \n",
    "        dfs([0], graph[0], len(graph)-1)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans,temp = [],[]\n",
    "        def dfs(i):\n",
    "            if i == len(graph) - 1:\n",
    "                ans.append(list(temp))\n",
    "                return\n",
    "            for y in graph[i]:\n",
    "                temp.append(y)\n",
    "                dfs(y)\n",
    "                temp.pop()\n",
    "        \n",
    "        temp.append(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        stk = []\n",
    "        def dfs(x:int):\n",
    "            if x == len(graph) - 1:\n",
    "                ans.append(stk[:])\n",
    "                return\n",
    "            \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans =[]\n",
    "        n=len(graph) -1\n",
    "        def dfs(x,path):\n",
    "            if x==n:\n",
    "                ans.append(path[:])\n",
    "            if graph[x]==[]:return \n",
    "\n",
    "            for i in graph[x]:\n",
    "                path.append(i)\n",
    "                dfs(i,path)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0,[0])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(graph)-1\n",
    "        res=[]\n",
    "        def dfs(begin, path):\n",
    "            # print(begin,path)\n",
    "            if begin == n:\n",
    "                res.append(path[:])\n",
    "                # print(path)\n",
    "                return\n",
    "            for x in graph[begin]:\n",
    "                # if x in path:\n",
    "                \n",
    "                dfs(x, path+[x])\n",
    "        dfs(0, [0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        stack = list()\n",
    "        \n",
    "        def dfs(n):\n",
    "            if n == len(graph) - 1:\n",
    "                ans.append(stack[:])\n",
    "                return\n",
    "            for pth in graph[n]:\n",
    "                stack.append(pth)\n",
    "                dfs(pth)\n",
    "                stack.pop()\n",
    "        stack.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        def dfs(path, idx):\n",
    "            if idx == len(graph) - 1:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(len(graph[idx])):\n",
    "                path.append(graph[idx][i])\n",
    "                dfs(path, graph[idx][i])\n",
    "                path.pop()\n",
    "        path.append(0)\n",
    "        dfs(path, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        road = [0]\n",
    "\n",
    "        def trackback():\n",
    "            if road[-1] == len(graph)-1:\n",
    "                res.append(road[:])\n",
    "            else:\n",
    "                for nxt in graph[road[-1]]:\n",
    "                    road.append(nxt)\n",
    "                    trackback()\n",
    "                    road.pop()\n",
    "        trackback()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(graph)\n",
    "        def dfs(idx, path):\n",
    "            nonlocal res\n",
    "            if idx==n-1:\n",
    "                res.append(list(path))\n",
    "                return\n",
    "            \n",
    "            for i in graph[idx]:\n",
    "                path.append(i)\n",
    "                dfs(i,path)\n",
    "                path.pop()\n",
    "        dfs(0,[0])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        q = deque([[0]])\n",
    "        ans = []\n",
    "        while q:\n",
    "            path = q.popleft()\n",
    "            node = path[-1]\n",
    "            if node == n-1:\n",
    "                ans.append(path)\n",
    "            for neighbori in graph[node]:\n",
    "                q.append(path+[neighbori])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        stack = [0]\n",
    "        graph_len = len(graph)\n",
    "        goal = graph_len-1\n",
    "        def traceback(i):\n",
    "            if stack[-1] == goal:\n",
    "                ans.append(stack[:])\n",
    "                return\n",
    "            for j in graph[i]:\n",
    "                stack.append(j)\n",
    "                traceback(j)\n",
    "                stack.pop()\n",
    "        traceback(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        result=[]\n",
    "        n=len(graph)\n",
    "\n",
    "        def traverse(path,node):\n",
    "            path.append(node)\n",
    "\n",
    "            if node==n-1:\n",
    "                result.append(path[:])\n",
    "                path.pop()\n",
    "                return\n",
    "\n",
    "            for cur_node in graph[node]:\n",
    "                traverse(path,cur_node)\n",
    "            \n",
    "            path.pop()\n",
    "        \n",
    "        traverse([],0)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        stk = []\n",
    "        def dfs(x:int):\n",
    "            if x==len(graph)-1:\n",
    "                ans.append(stk[:])\n",
    "                return\n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(x: int):\n",
    "            if x == len(graph) - 1:\n",
    "                ans.append(stk[:])\n",
    "                print(ans)\n",
    "                return\n",
    "         \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        nb = defaultdict(list)\n",
    "\n",
    "        for idx, ga in enumerate(graph):\n",
    "            for g in ga:\n",
    "                nb[idx].append(g)\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if node == n-1:\n",
    "                ans.append(tmp[:])\n",
    "                 \n",
    "            for ch in nb[node]:\n",
    "                tmp.append(ch)\n",
    "                dfs(ch)\n",
    "                tmp.pop()\n",
    "        tmp = [0]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        nb = defaultdict(list)\n",
    "\n",
    "        for idx, ga in enumerate(graph):\n",
    "            for g in ga:\n",
    "                nb[idx].append(g)\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if node == n-1:\n",
    "                ans.append(tmp[:])\n",
    "                return \n",
    "            for ch in nb[node]:\n",
    "                tmp.append(ch)\n",
    "                dfs(ch)\n",
    "                tmp.pop()\n",
    "        tmp = [0]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        \n",
    "        load = []\n",
    "        res = []\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i == n -1:\n",
    "                res.append(load[:])\n",
    "                return\n",
    "            for v in graph[i]:\n",
    "                load.append(v)\n",
    "                dfs(v)\n",
    "                load.pop()\n",
    "            \n",
    "        load.append(0)\n",
    "        dfs(0)\n",
    "        return res\n",
    "        # g = collections.defaultdict(list)\n",
    "        # for i, v in enumerate(graph):\n",
    "        #     for vv in v:\n",
    "        #         # if i  in g:\n",
    "        #         g[i].append(vv)\n",
    "        #         # else:\n",
    "        #         #     g[i] = [vv]\n",
    "        #     # print(g[i])\n",
    "        # visited = [False] * n\n",
    "        # def dfs(i, load):\n",
    "        #     nonlocal res\n",
    "        #     if g[i] == []:\n",
    "        #         # print(i)\n",
    "        #         res.append(load)\n",
    "        #         return\n",
    "        #     visited[i] = True\n",
    "        #     # if g[i]:\n",
    "        #     for v in g[i]:\n",
    "        #         if not visited[v]:\n",
    "        #             load.append(v)\n",
    "        #             dfs(v, load)\n",
    "        #             # load.pop()\n",
    "        # res = []\n",
    "        # for i in g[0]:\n",
    "        #     load = [0]\n",
    "        #     visited = [False] * n\n",
    "        #     visited[0] = True\n",
    "        #     visited[i] = True\n",
    "        #     dfs(i, load + [i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        ans = list()\n",
    "        visited = [0] * n  # initialzie the visited list\n",
    "\n",
    "        path = [0]\n",
    "\n",
    "        def dfs(u):\n",
    "            print(path)\n",
    "            if u == n - 1:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for edge in graph[u]:\n",
    "                path.append(edge)\n",
    "                dfs(edge)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        def dfs(idx:int):\n",
    "            res = []\n",
    "            if idx == n - 1:\n",
    "                return [[idx]]\n",
    "            for i in graph[idx]:\n",
    "                for j in dfs(i):\n",
    "                    res.append([idx]+j)\n",
    "            return res\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        nb = defaultdict(list)\n",
    "\n",
    "        for idx, ga in enumerate(graph):\n",
    "            for g in ga:\n",
    "                nb[idx].append(g)\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if node == n-1:\n",
    "                ans.append(tmp[:])\n",
    "                return \n",
    "            for ch in nb[node]:\n",
    "                tmp.append(ch)\n",
    "                dfs(ch)\n",
    "                tmp.pop()\n",
    "        tmp = [0]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(n):\n",
    "            if n == len(graph)-1:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in graph[n]:\n",
    "                path.append(i)\n",
    "                dfs(i)\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        path = [0]\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def bfs(src: int, dst: int, pre: List[List[int]]) -> List[List[int]]:\n",
    "            if src == dst:\n",
    "                return [[dst]]\n",
    "            a = []\n",
    "            for x in graph[src]:\n",
    "                # Cartesian product ***\n",
    "                # every path s from 0 to src\n",
    "                # every path t from src to dst\n",
    "                # generate path s+t from 0 to dst\n",
    "                a.extend([s + t for s in pre for t in bfs(x, dst, [[x]])])\n",
    "            return a \n",
    "        \n",
    "        return bfs(0, len(graph) - 1, [[0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def traverse(graph, node):\n",
    "            path.append(node)\n",
    "            if node == len(graph) - 1:\n",
    "                res.append(path[:])\n",
    "\n",
    "            for neighbor in graph[node]:\n",
    "                traverse(graph, neighbor)\n",
    "            path.pop()\n",
    "        \n",
    "        traverse(graph, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        stk = []\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == len(graph) - 1:\n",
    "                ans.append(stk[:])\n",
    "                return\n",
    "            \n",
    "            for y in graph[x]:\n",
    "                stk.append(y)\n",
    "                dfs(y)\n",
    "                stk.pop()\n",
    "        \n",
    "        stk.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        L=len(graph) \n",
    "        res=[]\n",
    "\n",
    "        def dfs(node,l):\n",
    "            if node==L-1:\n",
    "                res.append(l.copy())\n",
    "                return\n",
    "            for next_node in graph[node]:\n",
    "                l.append(next_node)\n",
    "                dfs(next_node,l)\n",
    "                l.pop()\n",
    "        dfs(0,[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        path = [0]\n",
    "        q = collections.deque([path])\n",
    "        res = []\n",
    "        while q:\n",
    "            path = q.popleft()\n",
    "            last_node = path[-1]\n",
    "            for node in graph[last_node]:\n",
    "                if node == n - 1:\n",
    "                    res.append(path + [node])\n",
    "                if node not in path:\n",
    "                    q.append(path + [node])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(n):\n",
    "            if n == len(graph)-1:\n",
    "                path.append(n)\n",
    "                res.append(path.copy())\n",
    "                path.pop()\n",
    "                return\n",
    "            for i in graph[n]:\n",
    "                path.append(n)\n",
    "                dfs(i)\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(idx:int) -> List[List[int]]:\n",
    "            res = []\n",
    "            if idx == len(graph) - 1:\n",
    "                return [[idx]]\n",
    "            for i in graph[idx]:\n",
    "                for j in dfs(i):\n",
    "                    res.append([idx]+j)\n",
    "            return res\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        n = len(graph)\n",
    "\n",
    "        def dfs(i):\n",
    "            stack.append(i)\n",
    "            if i == n - 1:\n",
    "                res.append(stack.copy())\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "            stack.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        route = []\n",
    "        num = len(graph)\n",
    "        def dfs(gragh, x, path):\n",
    "            if x==len(gragh)-1:\n",
    "                complete = path.copy()\n",
    "                route.append(complete)\n",
    "            if len(gragh[x]) == 0:\n",
    "                return\n",
    "            for j in gragh[x]:\n",
    "                path.append(j)\n",
    "                dfs(gragh, j, path)\n",
    "                path.pop()\n",
    "        path = []\n",
    "        path.append(0)\n",
    "\n",
    "        dfs(graph, 0, path)\n",
    "\n",
    "        return route"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # graph is a adjacency list\n",
    "        # just a simple dfs\n",
    "        all_paths = []\n",
    "        visited = [False] * len(graph)\n",
    "        def dfs(path: list):\n",
    "            # terminal condition\n",
    "            if path[-1] == len(graph) - 1:\n",
    "                all_paths.append(path)\n",
    "            # dfs next step\n",
    "            cur_node = path[-1]\n",
    "            for adj_node in graph[cur_node]:\n",
    "                if visited[adj_node]:\n",
    "                    continue\n",
    "                visited[adj_node] == True\n",
    "                dfs(path + [adj_node])  # watch out. Don't use same array in all layers in stack!\n",
    "                visited[adj_node] == False\n",
    "\n",
    "\n",
    "        visited[0] == True\n",
    "        dfs([0])\n",
    "        \n",
    "        return all_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(graph)\n",
    "        l=[]\n",
    "        res=[]\n",
    "        def dfs(index):\n",
    "            if index==n-1:\n",
    "                res.append(l.copy()+[index])\n",
    "                return \n",
    "            l.append(index)\n",
    "            for j in graph[index]:\n",
    "                dfs(j) \n",
    "            l.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(graph)\n",
    "        d = [0] * n\n",
    "        res = []\n",
    "        path = [0]\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == n - 1:\n",
    "                res.append(list(path))\n",
    "\n",
    "            for node in graph[x]:\n",
    "                if not d[node]:\n",
    "                    d[node] = 1\n",
    "                    path.append(node)\n",
    "                    dfs(node)\n",
    "                    d[node] = 0\n",
    "                    path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        paths = []\n",
    "        n = len(graph) - 1\n",
    "        def dfs(node: int, graph: List[List[int]], path: List[int]):\n",
    "            if node == n:\n",
    "                paths.append(path[:])\n",
    "            start = graph[node]\n",
    "            for i in start:\n",
    "                path.append(i)\n",
    "                dfs(i, graph, path)\n",
    "                path.pop()\n",
    "        dfs(0, graph, [0])\n",
    "        return paths\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for i in range(len(graph)):\n",
    "            dic[i] = graph[i]\n",
    "        \n",
    "        path = [0]\n",
    "        q = deque()\n",
    "        q.append((0,path))\n",
    "\n",
    "        target = len(graph) - 1\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            n = q.popleft()\n",
    "            node = n[0]\n",
    "            path = n[1]\n",
    "            if node == target:\n",
    "                res.append(path)\n",
    "            \n",
    "            for s in dic[node]:\n",
    "                temp = path[:]\n",
    "                temp.append(s)\n",
    "                q.append((s,temp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        res = []\n",
    "        l = len(graph)\n",
    "        visited = [0]*l\n",
    "        visited[0] = 1\n",
    "\n",
    "        def dfs(x):\n",
    "            visited[x] = 1\n",
    "            res.append(x)\n",
    "            if x!=l-1:\n",
    "                for i in graph[x]:\n",
    "                    if not visited[i]:\n",
    "                        dfs(i)\n",
    "            else:\n",
    "                ret.append(deepcopy(res))\n",
    "            visited[x] = 0\n",
    "            res.pop()\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        route = []\n",
    "        def dfs(gragh, x, path):\n",
    "            if x==len(gragh)-1:\n",
    "                complete = path.copy()\n",
    "                route.append(complete)\n",
    "            if len(gragh[x]) == 0:\n",
    "                return\n",
    "            for j in gragh[x]:\n",
    "                path.append(j)\n",
    "                dfs(gragh, j, path)\n",
    "                path.pop()\n",
    "        path = []\n",
    "        path.append(0)\n",
    "\n",
    "        dfs(graph, 0, path)\n",
    "\n",
    "        return route"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for i in range(len(graph)):\n",
    "            dic[i] = graph[i]\n",
    "        path =[0]\n",
    "        q = deque([(0,path)])\n",
    "        target = len(graph)-1\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            n=  q.popleft()\n",
    "            # print(n)\n",
    "            node = n[0]\n",
    "            path = n[1]\n",
    "            if node == target:\n",
    "                res.append(path)\n",
    "            \n",
    "            for s in dic[node]:\n",
    "                temp = path[:]\n",
    "                temp.append(s)\n",
    "                q.append((s,temp))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:\n",
    "        # dfs\n",
    "        ans, tempt = [], []\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(graph) - 1:\n",
    "                ans.append(tempt[:])\n",
    "                return \n",
    "            for y in graph[i]:\n",
    "                tempt.append(y)\n",
    "                dfs(y)\n",
    "                tempt.pop()\n",
    "        tempt.append(0)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
